package week02

// 130. 被围绕的区域
// https://leetcode-cn.com/problems/surrounded-regions/

func solve(board [][]byte) {
	var visit = make(map[int]bool)
	for row := range board {
		for col := range board[row] {
			if board[row][col] == 'O' && !visit[hash(row, col)] {
				ans, isEdge := dfs(board, visit, row, col, [][]int{}, false)
				if !isEdge {    // 不是边缘点
					for _, point := range ans {
						board[point[0]][point[1]] = 'X'
					}
				}
			}
		}
	}
}

func dfs(board [][]byte, visit map[int]bool, x, y int, ans [][]int, isEdge bool) ([][]int, bool) {
	visit[hash(x, y)] = true
	isEdge = isEdge || checkEdge(board, x, y)
	ans = append(ans, []int{x, y})

	for dir := range dx {
		nx := x + dx[dir]
		ny := y + dy[dir]
		if visit[hash(nx, ny)] {
			continue
		}
		// 有效性判断
		if !checkValid(board, nx, ny) {
			continue
		}


		if board[nx][ny] == 'O' {
			ans, isEdge = dfs(board, visit, nx, ny, ans, isEdge)
		}
	}
	return ans, isEdge
}

func checkEdge(board [][]byte, x, y int) bool {
	return x == 0 || y == 0 || x == len(board)-1 || y == len(board[x])-1
}

func checkValid(board [][]byte, x, y int) bool {
	return x >= 0 && y >= 0 && x < len(board) && y < len(board[x])
}


func hash(row, col int) int {
	return row * 300 + col
}

var dx = [4]int{0, 1, 0, -1}
var dy = [4]int{1, 0, -1, 0}